package aufgabe1;



import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author benjamin
 */
public class BinaryTree<T> extends Tree<T> {
    /*
     * Set LEFT and RIGHT for the children's index
     */

    protected static final int LEFT = 0;
    protected static final int RIGHT = 1;

    /*
     * Depth-Traversation types
     */
    private enum TraversationTyp {

        InOrder,
        PreOrder,
        PostOrder;
    };

    /**
     * Iterator for the binary tree
     *
     * @param <T>
     */
    private class BinaryTreeIterator<T> implements Iterator<T> {

        private Queue<Node> _queue = new LinkedList<Node>();
        private Iterator<Node> _it;

        public BinaryTreeIterator(TraversationTyp t) {
            _queue = depthTraversation(_root, t, _queue);
            _it = _queue.iterator();
        }

        @Override
        public boolean hasNext() {
            return _it.hasNext();
        }

        @Override
        public T next() {
            return (T)_it.next().getValue();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported yet.");
        }

    }

    /**
     * Constructor
     */
    public BinaryTree() {
        /*
         * Only two childrens
         */
        _maxChildrens = 2;
    }

    /**
     * Returns an iterator to traverse tree in In-Order mode
     *
     * @return
     */
    public Iterator<T> inOrderIterator() {
        return new BinaryTreeIterator(TraversationTyp.InOrder);
    }

    /**
     * Returns an iterator to traverse tree in Pre-Order mode
     *
     * @return
     */
    public Iterator<T> preOrderIterator() {
        return new BinaryTreeIterator(TraversationTyp.PreOrder);
    }

    /**
     * Returns an iterator to traverse tree in Post-Order mode
     *
     * @return
     */
    public Iterator<T> postOrderIterator() {
        return new BinaryTreeIterator(TraversationTyp.PostOrder);
    }

    /**
     * Depth traverse
     *
     * Recursive traversing
     *
     * @param root - root node
     * @param typ - InOrder, PreOrder, PostOrder
     * @param buffer - Empty list
     * @return - ordered list
     */
    private Queue<Node> depthTraversation(Node root, TraversationTyp typ, Queue<Node> buffer) {
        if (root == null) {
            /*
             * Rescursion stop
             */
            return buffer;
        }
        switch (typ) {
            /*
             * Recursion for every typ
             */
            case InOrder:
                buffer = depthTraversation(root.getChild(LEFT), typ, buffer);
                buffer.add(root);
                buffer = depthTraversation(root.getChild(RIGHT), typ, buffer);
                break;
            case PreOrder:
                buffer.add(root);
                buffer = depthTraversation(root.getChild(LEFT), typ, buffer);
                buffer = depthTraversation(root.getChild(RIGHT), typ, buffer);
                break;
            case PostOrder:
                buffer = depthTraversation(root.getChild(LEFT), typ, buffer);
                buffer = depthTraversation(root.getChild(RIGHT), typ, buffer);
                buffer.add(root);
                break;
        }
        return buffer;
    }

    
    /**
     * Convert this tree to a binary search tree.
     * 
     * Warning: After this operation this old tree is empty!
     * 
     * @param comparator - to compare values and build up the binary search tree
     * @return 
     */
    public BinarySearchTree<T> toBinarySearchTree(Comparator<T> comparator) {
        BinarySearchTree<T> bs = new BinarySearchTree<T>(comparator);
        Queue<Node> queue = new LinkedList<Node>();
        /*
         * Get all nodes in post order
         */
        queue = depthTraversation(_root, TraversationTyp.PostOrder, queue);
        /*
         * Go through nodes and "move" them to new tree
         */
        Iterator<Node> it = queue.iterator();
        while (it.hasNext()) {
            /*
             * Get next node and clean all child references
             */
            Node n = it.next();
            n.setChild(null, LEFT);
            n.setChild(null, RIGHT);
            /*
             * insert node on right position
             */
            bs._root = insertToBinarySearchTree(bs._root, n, comparator);
        }
        /*
         * Update stats for new tree
         */
        bs._depth = _depth;
        bs._leaves = _leaves;
        bs._nodes = _nodes;
        /*
         * clean old tree
         */
        _root = null;
        _depth = 0;
        _nodes = 0;
        _leaves = 0;
        
        return bs;
    }
    
    /**
     * Insert a given node to the right position on binary search tree
     * 
     * @param root - root node / start node
     * @param n - current node (recursion)
     * @param comparator - to compare node values
     * @return 
     */
    private Node insertToBinarySearchTree(Node<T> root, Node<T> n, Comparator<T> comparator) {
        if (root == null) {
            return n;
        }
        if (comparator.compare(n.getValue(), root.getValue()) <= 0) {
            root.setChild(insertToBinarySearchTree(root.getChild(LEFT), n, comparator), LEFT);
        } else {
            root.setChild(insertToBinarySearchTree(root.getChild(RIGHT), n, comparator), RIGHT);
        }
        return root;
    } 
    
}
